/*
给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：

字符串中的每个字符都应当是小写元音字母（'a', 'e', 'i', 'o', 'u'）
每个元音 'a' 后面都只能跟着 'e'
每个元音 'e' 后面只能跟着 'a' 或者是 'i'
每个元音 'i' 后面 不能 再跟着另一个 'i'
每个元音 'o' 后面只能跟着 'i' 或者是 'u'
每个元音 'u' 后面只能跟着 'a'
由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。

 

示例 1：

输入：n = 1
输出：5
解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。
示例 2：

输入：n = 2
输出：10
解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。
示例 3：

输入：n = 5
输出：68
 

提示：

1 <= n <= 2 * 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-vowels-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

// 动态规划
class Solution {
public:
    int countVowelPermutation(int n) {
        if (n == 1) {
            return 5;
        }
        vector<long long> pre_dp(5, 1);
        vector<long long> dp(5, 0);
        for (int i{2}; i <= n; ++i) {
            dp[0] = (pre_dp[1] + pre_dp[2] + pre_dp[4]) % MOD;
            dp[1] = (pre_dp[0] + pre_dp[2]) % MOD;
            dp[2] = (pre_dp[1] + pre_dp[3]) % MOD;
            dp[3] = pre_dp[2] % MOD;
            dp[4] = (pre_dp[2] + pre_dp[3]) % MOD;
            pre_dp = dp;
        }
        int res = accumulate(dp.begin(), dp.end(), 0LL) % MOD;
        return res;
    }
private:
    static constexpr long long MOD = 1e9 + 7;
};

// 矩阵快速幂
using LL = long long;
using Matrix = vector<vector<LL>>;

class Solution {
public:
    int countVowelPermutation(int n) {
        LL mod = 1e9 + 7;
        Matrix factor = {
            {0, 1, 0, 0, 0},
            {1, 0, 1, 0, 0},
            {1, 1, 0, 1, 1},
            {0, 0, 1, 0, 1},
            {1, 0, 0, 0, 0}
        };
        Matrix pow = fastPow(factor, n - 1, mod);
        LL res = 0;
        for (int i{0}; i < 5; ++i) {
            res = (res + accumulate(pow[i].begin(), pow[i].end(), 0LL)) % mod;
        }
        return res;
    }
private:
    Matrix fastPow(const Matrix& matrix, LL n, LL mod) {
        int m = matrix.size();
        Matrix res(m, vector<LL>(m, 0));
        Matrix cur = matrix;
        for (int i{0}; i < m; ++i) {
            res[i][i] = 1;
        }
        for (int i = n; i != 0; i >>= 1) {
            if (i & 1) {
                res = multiply(cur, res, mod);
            }
            cur = multiply(cur, cur, mod);
        }
        return res;
    }
    Matrix multiply(const Matrix& matrixA, const Matrix& matrixB, LL mod) {
        int m = matrixA.size();
        int n = matrixB.size();
        Matrix res(m, vector<LL>(n, 0));
        for (int i{0}; i < m; ++i) {
            for (int j{0}; j < n; ++j) {
                for (int k{0}; k < matrixA[i].size(); ++k) {
                    res[i][j] = (res[i][j] + matrixA[i][k] * matrixB[k][j]) % mod;
                }
            }
        }
        return res;
    }
};
